
#include <iostream>
using namespace std;

struct TreeNode 
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;

    TreeNode(int val = int())
        :val(val)
        , left(nullptr)
        , right(nullptr)
    {}
};

typedef struct TreeNode BTNode;

BTNode* CreateBTree(void)
{
    BTNode* node1 = new BTNode(1);
    BTNode* node2 = new BTNode(0);
    BTNode* node3 = new BTNode(1);
    BTNode* node4 = new BTNode(0);
    BTNode* node5 = new BTNode(1);
    BTNode* node6 = new BTNode(0);
    BTNode* node7 = new BTNode(1);

    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;

    return node1;
}

#include <math.h>
int _dfs(struct TreeNode* root, int* res)
{
    if (root == NULL)
        return 0;

    int left = _dfs(root->left, res);
    int right = _dfs(root->right, res);
    *res += abs(left - right);

    return left + right + root->val;
}

int findTilt(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    int res = 0;
    _dfs(root, &res);

    return res;
}

void _sum1(struct TreeNode* root, int add, unsigned int* sum)
{
    if (root == NULL)
        return;

    if (root->left == NULL && root->right == NULL)
    {
        (*sum) = *sum + add + root->val;
        return;
    }

    add += root->val;
    _sum1(root->left, add << 1, sum);
    _sum1(root->right, add << 1, sum);
}

int sumRootToLeaf1(struct TreeNode* root)
{
    unsigned int sum = 0;

    _sum1(root, 0, &sum);

    return sum;
}

void _sum2(struct TreeNode* root, int pathval, unsigned int* sum)
{
    if (root == NULL)
        return;

    pathval = (pathval << 1) + root->val;

    if (root->left == NULL && root->right == NULL)
    {
        *sum += pathval;
        return;
    }

    _sum2(root->left, pathval, sum);
    _sum2(root->right, pathval, sum);
}

int sumRootToLeaf2(struct TreeNode* root)
{
    unsigned int sum = 0;

    _sum2(root, 0, &sum);

    return sum;
}

void Test1()
{
    BTNode* root = CreateBTree();

    cout << sumRootToLeaf1(root) << endl;
}

int main()
{
    Test1();

	return 0;
}